package main

import (
	"fmt"
	"math"
)

func main() {
	var v = []int{2, 4, 1, 3, 2, 3}
	var w = []int{3, 4, 9, 2, 1, 5}
	//fmt.Println(recMaxValue(4, v, w, 10))

	fmt.Println(dpMaxValue(v, w, 10))
}

//func recMaxValue(i int, v []int, w []int, W int) int {
//	if i == 0 {
//		return 0
//	} else if W == 0 {
//		return 0
//	} else {
//		if w[i] > W {
//			return recMaxValue(i-1, v, w, W)
//		} else {
//			a := recMaxValue(i-1, v, w, W) //没选
//			b := recMaxValue(i-1, v, w, W-w[i]) + v[i]
//
//			return int(math.Max(float64(a), float64(b)))
//		}
//	}
//}

//将前i件物品放入容量为v的背包中
func dpMaxValue(v []int, w []int, W int) int {
	subset := make([][]int, len(v))
	for x := 0; x < len(v); x++ {
		subset[x] = make([]int, W)
	}

	for y := 0; y < W; y++ {
		subset[0][y] = 0
	}
	for x := 1; x < len(v); x++ {
		for y := 1; y < W; y++ {
			if w[x] > y {
				subset[x][y] = subset[x-1][y]
			} else {
				a := subset[x-1][y]
				b := subset[x-1][y-w[x]] + v[x]
				subset[x][y] = int(math.Max(float64(a), float64(b)))
			}
		}
	}

	return subset[len(v)-1][W-1]
}
